use crate::hot100::base::{ListNode, Vec2ListNode};

#[test]
fn test_is_palindrome() {
    let node = ListNode::new(-1);
    assert_eq!(is_palindrome(node.from_vec(vec![1, 2])), false);

    assert_eq!(is_palindrome(node.from_vec(vec![1, 2, 2, 1])), true);

    assert_eq!(is_palindrome(node.from_vec(vec![1])), true);
}
/*
    234. 回文链表
    请判断一个链表是否为回文链表。
    示例 1:
    输入: 1->2
    输出: false

    示例 2:
    输入: 1->2->2->1
    输出: true

    进阶：
    你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
*/
pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
    if head.is_none() {
        return true;
    }

    let mut vec = Vec::new();
    let mut current = head;
    while let Some(mut node) = current.take() {
        let next = node.next.take();
        vec.push(node.val);
        current = next;
    }

    if vec.len() == 1 {
        return true;
    }

    let q = vec.len() - 1;
    let n = vec.len() / 2;
    for i in 0..n {
        if vec[i] != vec[q - i] {
            return false;
        }
    }
    return true;
}
